package lru;

import java.util.HashMap;
import java.util.Objects;

/**
 * @Author Chill_Lyn
 * @Date 2021/3/22 22:28
 */
public class LRU<K, V> {

    /**
     * 存储节点容器
     */
    private final HashMap<K, Node<K, V>> caches;
    /**
     * 总容量
     */
    private final int capacity;
    /**
     * 头结点
     */
    private Node<K, V> first;
    /**
     * 尾结点
     */
    private Node<K, V> last;

    public LRU(int size) {
        this.capacity = size;
        caches = new HashMap<K, Node<K, V>>(size);
    }

    public static void main(String[] args) {
        LRU<Integer, String> lru = new LRU<Integer, String>(5);
        lru.put(1, "a");
        lru.put(2, "b");
        lru.put(3, "c");
        lru.put(4, "d");
        lru.put(5, "e");
        System.out.println("原始链表为:" + lru.toString());

        System.out.println(lru.get(4));
        System.out.println("获取key为4的元素之后的链表:" + lru.toString());

        lru.put(6, "f");
        System.out.println("新添加一个key为6之后的链表:" + lru.toString());

        System.out.println(lru.remove(3));
        System.out.println("移除key=3的之后的链表:" + lru.toString());
    }

    /**
     * 放入元素
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {

        Node<K, V> node = caches.get(key);
        //如果存在元素，替换值
        if (Objects.nonNull(node)) {
            node.value = value;
        }

        // 如果超过元素容纳量
        if (caches.size() >= capacity) {
            //移除最后一个节点
            caches.remove(last.key);
            removeLast();
        }
        //创建新节点
        node = new Node<K, V>(key, value);
        //移到头节点
        moveToHead(node);
        caches.put(key, node);
    }

    /**
     * 通过key获取元素
     *
     * @param key
     * @return
     */
    public Object get(K key) {
        Node<K, V> node = caches.get(key);
        if (node == null) {
            return null;
        }
        //把访问的节点移动到首部
        moveToHead(node);
        return node.value;
    }

    /**
     * 根据key移除节点
     *
     * @param key
     * @return
     */
    public Object remove(K key) {
        Node<K, V> node = caches.get(key);
        if (node != null) {
            if (node == first) {
                first = node.next;
                first.pre = null;
            }

            if (node == last) {
                last = node.pre;
                last.next = null;
            }

            if (node.pre != null) {
                node.pre.next = node.next;
            }

            if (node.next != null) {
                node.next.pre = node.pre;
            }
            node.pre = null;
            node.next = null;
        }
        return caches.remove(key);
    }

    /**
     * 清除所有节点
     */
    public void clear() {
        first = null;
        last = null;
        caches.clear();
    }

    /**
     * 把当前节点移动到首部
     *
     * @param node
     */
    private void moveToHead(Node<K, V> node) {
        if (first == null || last == null) {
            first = last = node;
            return;
        }
        if (first == node) {
            return;
        }
        if (node == last) {
            last = last.pre;
        }
        if (node.next != null) {
            node.next.pre = node.pre;
        }
        if (node.pre != null) {
            node.pre.next = node.next;
        }
        node.next = first;
        first.pre = node;
        first = node;
        first.pre = null;
    }

    /**
     * 移除最后一个节点
     */
    private void removeLast() {
        if (Objects.isNull(last)) {
            return;
        }

        if (last.equals(first)) {
            first = last = null;
        }

        last = last.pre;
        last.next = null;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node<K, V> node = first;
        while (node != null) {
            sb.append(String.format("%s:%s ", node.key, node.value));
            node = node.next;
        }
        return sb.toString();
    }
}
